11088 - End up with more teams (DP), 11282 - Mixing invitations & 1481 - Arrange...

[and.git] / Mi manual de algoritmos / version_maraton_interuniversitaria_2008-2 / src / geometria / grahamscan.tex

% Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite

{\ttfamily \raggedright {
\noindent
\mbox{}\textit{\textcolor{Brown}{/*}} \\
\mbox{}\textit{\textcolor{Brown}{\ \ Graham\ Scan.}} \\
\mbox{}\textit{\textcolor{Brown}{\ */}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$algorithm$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iterator$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$math.h$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$stdio.h$>$}} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{double}\ pi\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{2}\textcolor{BrickRed}{*}\textbf{\textcolor{Black}{acos}}\textcolor{BrickRed}{(}\textcolor{Purple}{0}\textcolor{BrickRed}{);} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{struct}}\ point\textcolor{Red}{\{} \\
\mbox{}\ \ \textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{,}y\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{()}\ \textcolor{Red}{\{\}} \\
\mbox{}\ \ \textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ X\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ Y\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Black}{x}}\textcolor{BrickRed}{(}X\textcolor{BrickRed}{),}\ \textbf{\textcolor{Black}{y}}\textcolor{BrickRed}{(}Y\textcolor{BrickRed}{)}\ \textcolor{Red}{\{\}} \\
\mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}point\ pivot\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}ostream\textcolor{BrickRed}{\&}\ \textbf{\textcolor{Blue}{operator}}\textcolor{BrickRed}{$<$$<$}\ \textcolor{BrickRed}{(}ostream\textcolor{BrickRed}{\&}\ out\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\textcolor{BrickRed}{\&}\ c\textcolor{BrickRed}{)} \\
\mbox{}\textcolor{Red}{\{} \\
\mbox{}\ \ out\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{"{}("{}}}\ \textcolor{BrickRed}{$<$$<$}\ c\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{"{},"{}}}\ \textcolor{BrickRed}{$<$$<$}\ c\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{"{})"{}}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ out\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{inline}}\ \textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{distsqr}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ b\textcolor{BrickRed}{.}x\textcolor{BrickRed}{)*(}a\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ b\textcolor{BrickRed}{.}x\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{+}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{-}\ b\textcolor{BrickRed}{.}y\textcolor{BrickRed}{)*(}a\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{-}\ b\textcolor{BrickRed}{.}y\textcolor{BrickRed}{);} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{inline}}\ \textcolor{ForestGreen}{double}\ \textbf{\textcolor{Black}{dist}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Black}{sqrt}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{distsqr}}\textcolor{BrickRed}{(}a\textcolor{BrickRed}{,}\ b\textcolor{BrickRed}{));} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\textit{\textcolor{Brown}{//retorna\ $>$\ 0\ si\ c\ esta\ a\ la\ izquierda\ del\ segmento\ AB}} \\
\mbox{}\textit{\textcolor{Brown}{//retorna\ $<$\ 0\ si\ c\ esta\ a\ la\ derecha\ del\ segmento\ AB}} \\
\mbox{}\textit{\textcolor{Brown}{//retorna\ ==\ 0\ si\ c\ es\ colineal\ con\ el\ segmento\ AB}} \\
\mbox{}\textbf{\textcolor{Blue}{inline}}\ \textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{cross}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}c\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}b\textcolor{BrickRed}{.}x\textcolor{BrickRed}{-}a\textcolor{BrickRed}{.}x\textcolor{BrickRed}{)*(}c\textcolor{BrickRed}{.}y\textcolor{BrickRed}{-}a\textcolor{BrickRed}{.}y\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{-}\ \textcolor{BrickRed}{(}c\textcolor{BrickRed}{.}x\textcolor{BrickRed}{-}a\textcolor{BrickRed}{.}x\textcolor{BrickRed}{)*(}b\textcolor{BrickRed}{.}y\textcolor{BrickRed}{-}a\textcolor{BrickRed}{.}y\textcolor{BrickRed}{);} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\textit{\textcolor{Brown}{//Self\ $<$\ that\ si\ esta\ a\ la\ derecha\ del\ segmento\ Pivot-That}} \\
\mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Black}{angleCmp}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}self\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}that\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \textcolor{ForestGreen}{int}\ t\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{cross}}\textcolor{BrickRed}{(}pivot\textcolor{BrickRed}{,}\ that\textcolor{BrickRed}{,}\ self\textcolor{BrickRed}{);} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}t\ \textcolor{BrickRed}{$<$}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}t\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textit{\textcolor{Brown}{//Self\ $<$\ that\ si\ está\ más\ cerquita}} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{distsqr}}\textcolor{BrickRed}{(}pivot\textcolor{BrickRed}{,}\ self\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ \textbf{\textcolor{Black}{distsqr}}\textcolor{BrickRed}{(}pivot\textcolor{BrickRed}{,}\ that\textcolor{BrickRed}{));} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ \textbf{\textcolor{Black}{graham}}\textcolor{BrickRed}{(}vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ p\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//Metemos\ el\ más\ abajo\ más\ a\ la\ izquierda\ en\ la\ posición\ 0}} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{$<$}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{$|$$|$}\ \textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{==}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{\&\&}\ p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}x\ \textcolor{BrickRed}{$<$}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{].}x\ \textcolor{BrickRed}{))} \\
\mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{swap}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{],}\ p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]);} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\ \  \\
\mbox{}\ \ pivot\ \textcolor{BrickRed}{=}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{];} \\
\mbox{}\ \ \textbf{\textcolor{Black}{sort}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{(),}\ p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{(),}\ angleCmp\textcolor{BrickRed}{);} \\
\mbox{} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//Ordenar\ por\ ángulo\ y\ eliminar\ repetidos.}} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//Si\ varios\ puntos\ tienen\ el\ mismo\ angulo\ el\ más\ lejano\ queda\ después\ en\ la\ lista}} \\
\mbox{}\ \ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ \textbf{\textcolor{Black}{chull}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{(),}\ p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{()+}\textcolor{Purple}{3}\textcolor{BrickRed}{);} \\
\mbox{} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//Ahora\ sí!!!}} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{3}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}\ chull\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{()}\ \textcolor{BrickRed}{$>$=}\ \textcolor{Purple}{2}\ \textcolor{BrickRed}{\&\&}\ \textbf{\textcolor{Black}{cross}}\textcolor{BrickRed}{(}chull\textcolor{BrickRed}{[}chull\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{()-}\textcolor{Purple}{2}\textcolor{BrickRed}{],}\ chull\textcolor{BrickRed}{[}chull\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{()-}\textcolor{Purple}{1}\textcolor{BrickRed}{],}\ p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{])}\ \textcolor{BrickRed}{$<$=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ chull\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{erase}}\textcolor{BrickRed}{(}chull\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{()}\ \textcolor{BrickRed}{-}\ \textcolor{Purple}{1}\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ chull\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]);} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//chull\ contiene\ los\ puntos\ del\ convex\ hull\ ordenados\ anti-clockwise.}} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//No\ contiene\ ningún\ punto\ repetido.}} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//El\ primer\ punto\ no\ es\ el\ mismo\ que\ el\ último,\ i.e,\ la\ última\ arista}} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//va\ de\ chull[chull.size()-1]\ a\ chull[0]}} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ chull\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{Red}{\}} \\

} \normalfont\normalsize